package ahjava.p12exercises.algorithm;
import java.util.Arrays;
public class T002背包问题 {
	// 阿里巴巴，见山洞有财宝n件，重量w，价值v
	// 毛驴能运的重量为m，财宝可以砸开。问：如何带走价值最大的宝贝？
	// 策略1：选价值最大——承重能力有限，不行
	// 策略2：选重量最小——可能没价值，不行
	// 策略3：选单位重量价值最大（cost performance）
	// 物品可以分割，是为“背包问题”。物品不可分割为“0-1背包问题”，贪心不能得最优解
	// 第一组：
	static int m = 30;
	static int[] w = { 4, 2, 9, 5, 5, 8, 5, 4, 5, 5 };
	static int[] v = { 3, 8, 18, 6, 8, 20, 5, 6, 7, 15 };
	// 第二组：
	// static int m = 19;
	// static int[] w = { 2, 6, 7, 4, 10, 3 };
	// static int[] v = { 8, 1, 9, 3, 2, 4 };
	static class Goods implements Comparable<Goods> {
		public Goods() {
			super();
		}
		int w;
		int v;
		Double cost_performance;
		@Override
		public String toString() {
			return "Goods [w=" + w + ", v=" + v + ", cost_performance=" + cost_performance + "]";
		}
		@Override
		public int compareTo(Goods o) {
			return -this.cost_performance.compareTo(o.cost_performance);
 		}
	}
	public static void main(String[] args) {
		int len = w.length;
		Goods[] g = new Goods[len];
		for (int i = 0; i < g.length; i++) {
			Goods _g = new Goods();
			_g.w = w[i];
			_g.v = v[i];
			_g.cost_performance = (double) v[i] / w[i];
			g[i] = _g;
		}
		// 按性价比排序
		Arrays.sort(g);
		// 装载
		double count = 0, countW = 0, countV = 0;
		double remainCount = 0.0, remainW = 0.0, remainV = 0.0;
		for (Goods _g : g) {
			if (countW + _g.w <= m) {
				System.out.println(_g);
				count++;
				countW += _g.w;
				countV += _g.v;
			} else if (countW < m) {
				remainW = m - countW;
				remainCount = remainW / _g.w;
				remainV = _g.v * remainCount;
				count += remainCount;
				countW += remainW;
				countV += remainV;
			}
		}
		System.out.println("共装入" + count + "件");
		System.out.println("总重量" + countW);
		System.out.println("总价值" + countV);
	}
}
